package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 生成不含相邻零的二进制字符串
 */

public class Code3211 {
    public static void main(String[] args) {
        int n = 6;
        System.out.println(new Code3211().validStrings(n));
    }

    public List<String> validStrings(int n) {
        List<String> ans = new ArrayList<>();
        StringBuilder cur = new StringBuilder();

        backtrace(0, cur, ans, n);
        return ans;
    }

    public void backtrace(int index, StringBuilder cur, List<String> ans, int n) {
        if (index == n) {
            ans.add(cur.toString());
            return;
        }

        if (cur.isEmpty() || cur.charAt(cur.length() - 1) == '1') {
            cur.append('0');
            backtrace(index + 1, cur, ans, n);
            cur.deleteCharAt(cur.length() - 1);
        }

        cur.append('1');
        backtrace(index + 1, cur, ans, n);
        cur.deleteCharAt(cur.length() - 1);
    }
}
